The present invention relates to a method to forward a multicast packet in a connectionless multicast system according to claim 1 and to an ingress node and a router realizing such a method according to claim 7 and to claim 8, respectively, and to an internet network including such an ingress node or such a router according to claim 10.
Such a method is already known in the art, e.g. from the Article xe2x80x98Datagrom Routing for Internet Multicastingxe2x80x99 written by Lorenzo Aguilar, SRI International , Menlo Park Calif., and published in the proceedings of Sigcomm84 in March 1984, ACM 0-8791-136-9/84/006/0058 page 58 to 62.
Therein a solution to the problem of multidestination routing in internetworks is described. More particular, at page 59, third paragraph, the so called xe2x80x98multidestination addressingxe2x80x99 is described. Such an algorithm places all its destination addresses in an Internet Packet. During propagation, the packet is replicated at gateways, called hereafter routers, and the address list is partitioned among the newly created packets, according their next internet stop. In this way, at each router the next hop for each destination is determined and per next hop a new header is constructed that contains only these destinations for which that next hop is on the shortest path to these destinations. This approach is called in the claims connectionless multicast system.
A problem outstanding with such a connectionless multicast system is however that the forwarding process in the different routers requires, a number of times, the consultation of the unicast routing table whereby this look-up and the re-construction of the packet headers consumes too much processing time. Hereby the wire-speed forwarding can not be achieved.
An object of the present invention is to provide a method to forward a multicast packet in a connectionless multicast system from an ingress node via a router to a plurality of destinations that does not have the above problem of consuming too much processing for the number of look-ups to the unicast routing table and the re-construction of the packet headers.
According to the present invention this object is achieved with the method of claim 1 which is realized by the ingress node and the router of claim 7 and claim 8, respectively and by the internet network that includes such an ingress node and such a router of claim 10.
Indeed, the object is achieved due to the fact that the method, according to claim 1, comprises the steps:
a) storing by the router in a memory a relation between a value of a receiver update notification and a predefined construction set. The predefined construction set includes a set of next hops that includes one or more next hops. The next hops are determined for each destination of a predefined set of destinations. The next hops are determined according to look-ups to local unicast routing information. The predefined set of destinations e.g. the destinations received within the header of a multicast packet includes only these destinations of the plurality of destinations for which the router is on a path to these destinations.
b) associating by the ingress node to a starting destination set the value of the receiver update notification. Such a starting destination set includes each one of the plurality of destinations. The ingress node furthermore includes this value of the receiver update notification in the multicast packet in order to be forwarded together with the multicast packet; and
c) by the router, upon reception of the multicast packet that includes the value of the receiver update notification, determining a predefined subset of destinations; and determining for the predefined subset of destinations a next hop of the set of next hops according to the value of the receiver update notification and according to the relation to the predefined construction set; and including in the multicast packet the predefined subset of destinations and the value of the receiver update number; and forwarding the multicast packet towards the next hop, the predefined subset of destinations includes these destinations of the plurality of destinations for which the next hop is on a path to these destinations.
Indeed, in this way the ingress node puts the value of the receiver update notification in e.g. the destination address and uses this same number for the following multicast packets whereby a router according to the present invention forwards the multicast packets according to the associated construction set in its memory. Each time the set of destinations changes, the ingress node indicates this to the downstream routers by updating and using a new value for the receiver update notification whereby the router is flagged to adapt the construction set by consulting, only then, the unicast routing table.
It has to be remarked here that the use of a value of the receiver update number is not necessary in order to forward a multicast packet. Indeed, once a value has been defined by the ingress node and has been forwarded to the routers, the value might be used to improve the forwarding process of the routers but is not essential to forward the multicast packets towards the different destinations.
A further remark is that as well traditional routers and routers according to the present invention might be used simultaneous in the network. Indeed, in the event of a traditional router that not works with a memory for storing the relations between receiver update notification and construction set, the router is still able to forward the multicast packets according to the prior art connectionless multicast procedures. Such a router just ignores the inclusion of such a receiver update notification in the multicast packet. On the other hand, a router according to the present invention will use the presence of a value for the receiver update notification and is enabled to improve its forwarding process.
Furthermore, it has to be remarked that the expression xe2x80x98is on a path to these destinationsxe2x80x99 is used in the application to mention the route from the ingress node to the destinations. Hereby it has to be understood that usual a shortest path is used for the routing of the multicast packets from the ingress node to the destinations. However the use of another predefined path from the ingress node to the different destinations that depends upon other kinds of criteria e.g. delay and bandwidth in order to be determined is not excluded by the present invention.
It has to be remarked that a clear difference arises between a receiver update notification and a multicast group number. Indeed, the receiver update notification is a reference to a construction set that includes information from the unicast routing tables but that is not essential to be used to forward the multicast packets. Whereas a multicast group number is a reference to information in a multicast routing table that is essential to be looked up in order to forward the multicast packets.
A further remark is that it has to be understood that the expression xe2x80x98including e.g. a subset of destinations or a receiver update numberxe2x80x99 means that at least a reference to such destination of the subset of destinations or a reference to the receiver update number is included in the internet multicast packet at a predefined appropriate place.
Yet, a remark is that an ingress node is defined as being the first node, for distributing the multicast packets, of a domain of nodes. Such nodes might be routers or hosts whereby an ingress node can be a host or a router.
Furhtermore, it has to be remarked that according to step c) the multicast packet is forwarded towards the next hop. In fact, it is not the multicast packet but a replication i.e. a copy of the payload of the packet and a reconstruction of the header of the packet that is forwarded to the next hop. This is known according to the working of connectionless multicast system, but however, goes beyond the scope of the invention. The aim is that a replicate of the multicast packet is forwarded to the next hops but is recalled, in order not to overload the text, multicast packet.
Yet, it has to be remarked that an implementation with different next hops coupled to one output link of the router is not excluded e.g. an Ethernet link.
A further feature of the present invention is described in claim 2. Herein it is described that in the event of more than one next hop being included in the set of next hops, the predefined construction set further includes a destination relation between each next hop and the predefined subset of destinations. Hereby the step of determining the predefined subset of destinations is realized according to this destination relation. Indeed, since more than one next hop is involved to forward the multicast packet to, the partitioning of the destinations over the different constructed new headers must be determined. This might be realized according to the destination relation.
Furthermore, according to claim 3, in the event of only one next hop being included in the set of next hops, the predefined subset of destinations might be determined by a received set of destinations being included in the received multicast packet. Indeed, since only one next hop is involved to forward the multicast packet to, determination of the newly subset of destinations to be included in the newly reconstructed header is realized by taking over the received set of destinations in the received multicast packet.
Another characteristic feature is described in claim 4. In the event when the value of the receiver update notification and the predefined set of destinations was already included in a previously received multicast packet the set of next hops can be determined according to this set of destinations. The predefined construction set is constructed for each next hop according to unicast routing information and for each next hop a subset of destinations is determined i.e. destination relation. The relation between the value of the receiver update notification and the predefined construction set is established and hereby the step a) of the method of the invention is executed upon reception of this previously received multicast packet.
It has to be remarked here that a previously packet is not necessary the multicast packet that was forwarded just before the actual multicast packet and that is neither the first packet of the multicast session with this set of starting destinations. Indeed, other elements might be important to decide during the connectionless multicast forwarding process the use of the receiver update notification e.g. the actual load of the network or the processing load of the ingress node. The aim is that at a predefined moment a value for the receiver update notification is determined and is associated to a starting set of destinations. From then on, this value might be included, on regular or on rather irregular base, into the multicast packets in order to enable the routers to improve its forwarding process.
Furthermore, claim 5 describes a situation whereby upon reception of a following multicast packet that includes a second value of the receiver update notification and that is associated to another starting destination set e.g. an extended starting destination set, the router has no relation stored in its memory. In this case, the following multicast packet is forwarded according to connectionless multicast procedures and step a) is executed for this second value of the receiver update notification and a second construction set (CS2). This means that the unicast routing table is consulted to construct again a new construction set according to the set of next hops and eventually according to a new subset of destinations. The construction set is saved and referred by the newly received second value of the receiver update notification. The second value of the receiver update notification and the new subsets of destinations are included in the following multicast packet and are routed towards the different hops according to the usual connectionless multicast system.
Finally, it has to be explained that as long that only one ingress node is included in the network to provide the multicast packets, the relation between the receiver update notification and the construction set can be determined unambiguous by reference to the value of the receiver update notification; However, in most networks more than one ingress node is included to provide the service of multicast sessions. In such networks it is clear that the relation to a construction set is identified by a unique combination of a value of the receiver update notification and a network internet address of the ingress node. This is described in claim 6.
It should be noticed that the term xe2x80x9ccomprisingxe2x80x9d, used in the claims, should not be interpreted as being limitative to the means listed thereafter. Thus, the scope of the expression xe2x80x9ca device comprising means A and Bxe2x80x9d should not be limited to devices consisting only of components A and B. It means that with respect to the present invention, the only relevant components of the device are A and B.
Similarly, it is to be noted that the term xe2x80x9ccoupledxe2x80x9d, also used in the claims, should not be interpreted as being limitative to direct connections only. Thus, the scope of the expression xe2x80x9ca device A coupled to a device Bxe2x80x9d should not be limited to devices or systems wherein an output of device A is directly connected to an input of device B. It means that there exists a path between an output of A and in input of B which may be a path including other devices or means.